/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mamayukero.logic.pathfinding;

import java.awt.Point;
import java.util.ArrayList;
import mamayukero.debug.LogContainer;
import mamayukero.problem.environment.map.Map;
import mamayukero.problem.environment.map.Path;

public class AStar extends PathFindingBase {
    
    public AStar (Map map) {
        super(map);
        log = new LogContainer("A*");
    }
    
    @Override
    public Path solve(Point start, Point end) {
        this.start = start;
        this.end = end;
        path = new Path(start,end);
        log.append("Mencari jalan dari [" + start.x + "," + start.y + "]" + " ke " + "[" + end.x + "," + end.y + "]");
        pathlist.clear();
        solve();
        StringBuilder pathString = new StringBuilder("Menemukan jalan : ");
        for (Point p: pathlist) {
            pathString.append("[").append(p.x).append(",").append(p.y).append("]");
        }
        log.append(pathString.toString());
        path.setPoint(pathlist);
        return path;
    }
    
    public void solve() {
        ArrayList<Point> LoV = new ArrayList<Point>();
        ArrayList<Point> LoE = new ArrayList<Point>();
        
        pathlist = solverecc(start, LoV, LoE);
        if (!pathlist.isEmpty()) {
            validateAns(pathlist);
            validateAgain(pathlist);
            path.setPoint(pathlist);
        } else {
            System.out.println("NO SOLUTION AVAILABLE");
        }
    }
    
    public void validateAns(ArrayList<Point> P) {
                
        for (int n=P.size()-1;n>0;n--) {
            if (distance(P.get(n),P.get(n-1)) != 1) {
                while (distance(P.get(n),P.get(n-1)) != 1) {
                    P.remove(n-1);
                    n--;
                }
            }
        }
    }
    
    
    public void validateAgain(ArrayList<Point> P) {
        ArrayList<Point> T = new ArrayList<Point>();
        boolean found = false;
        
        
        if (P.size()>3) {
            int i = 2;
            while ((distance(P.get(0),P.get(i)) != 1) && (i < (P.size())-1)) {
                i++;
            }
            
            if (i!=P.size()-1) {
                for (int id=1;id<i;id++) {
                    T.add(P.get(id));
                }
            }
            if (T.size()!=0) {
                for (Point Pt : T) {
                    P.remove(P.indexOf(Pt));
                }
            }
           
        }
        
        
        
        
        
    }
    
    ArrayList<Point> solverecc(Point input, ArrayList<Point> LoV, ArrayList<Point> LoE) {
        ArrayList<Point> PNS = new ArrayList<Point>(); // possible next steps
        
        pathlist.add(input);
        LoV.add(input);
        PNS = whereToGo(input.x, input.y, map); // generate all possible steps
        validate(PNS, LoV, LoE); // remove visited or expanded coordinate from PNS
        
        if (PNS.isEmpty()) { //no possible next steps exist
                        
            LoV.add(input); // put input into list of visited
            
            if (LoE.isEmpty()) { //no block-to-expand exist
            
                ArrayList<Point> empty = new ArrayList<Point>();
                return empty; // no solutions available
            
            } else {
            
                Point cLoE = findCheapest(LoE);
                LoE.remove(LoE.indexOf(cLoE));
                    
                if (isSol(cLoE)) { // cLoE is the solution
                    
                    pathlist.add(cLoE);
                    return pathlist;
                
                } else {
                    
                    solverecc(cLoE,LoV,LoE);
                    
                }
            }
                
        } else {
            
            Point cPNS = findCheapest(PNS);
            
            if (LoE.isEmpty()) { // no block-to-expand exist
                
                PNS.remove(PNS.indexOf(cPNS));
                LoE.addAll(PNS);
                               
                if (isSol(cPNS)) { // cPNS is the solution

                    pathlist.add(cPNS);
                    return pathlist;

                } else {
                    
                    solverecc(cPNS, LoV, LoE);
                    
                }
                
            } else {
                
                Point cLoE = findCheapest(LoE);
                double fcloe = f(cLoE), fcpns = f(cPNS);
                
                if (fcloe > fcpns) { // pick cPNS
                    
                    PNS.remove(cPNS);
                    LoE.addAll(PNS);
                    
                    if (isSol(cPNS)) { // cPNS is the solution 
                        
                        pathlist.add(cPNS);
                        return pathlist;
                        
                    } else {
                        
                        solverecc(cPNS, LoV, LoE);
                        
                    }
                    
                } else { // pick cLoE
                    
                    LoE.addAll(PNS);
                    LoE.remove(LoE.indexOf(cLoE));
                                                          
                    if (isSol(cLoE)) { // cLoE is the solution
                        
                        pathlist.add(cLoE);
                        return pathlist;
                        
                    } else {
                        
                        solverecc(cLoE, LoV, LoE);
                        
                    }
                                        
                }
                
            }
            
        }
        
        return pathlist;
    }
    
    Point findCheapest(ArrayList<Point> input) {
        Point result = new Point();
        ArrayList<Point> temp = new ArrayList<Point>();
        
        result = input.get(0);
        for (Point it : input) {
            
            if (f(it) <= f(result)) {
                result = it;
            }
        }
        
        return result;
    }
    
    public double f(Point P) {
        //f = g + h
        //float g,h;
        
        //g = P.x - end.x;
        //h = P.y - end.y;
        return Point.distance(P.x, P.y, end.x, end.y) + Point.distance(P.x, P.y, start.x, start.y);
        
        //return (g+h);       
    }
    
    public int distance(Point inp, Point target) {
        
        return Math.abs(inp.x - target.x) + Math.abs(inp.y - target.y);
    }
    
    boolean isSol(Point P) {
        return P.equals(end);       
    }
    
    public void validate(ArrayList<Point> PNS, ArrayList<Point> LoV, ArrayList<Point> LoE) {
        
        ArrayList<Point> temp = new ArrayList<Point>();
        
        for (Point it : PNS) {
            if ((LoV.contains(it)) || (LoE.contains(it))) {
                temp.add(it);
            }
        }
        
        for (Point it : temp) {
            //try {
                PNS.remove(it);
            //} catch (IndexOutOfBoundsException bo) {
              //  System.out.println("[ERROR ASTAR] OUT OF BOUND = " + idx);
            //}
        }
        
    }
    
    
}
